Repairing Reed-Solomon Codes With Multiple Erasures

摘要

Despite their exceptional error-correcting properties, Reed-Solomon (RS)codes have been overlooked in distributed storage applications due to thecommon belief that they have poor repair bandwidth: A naive repair approachwould require the whole file to be reconstructed in order to recover a singleerased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16)proposed a single-erasure repair method for RS codes that achieves the optimalrepair bandwidth amongst all linear encoding schemes. Their key idea is torecover the erased symbol by collecting a sufficiently large number of itstraces, each of which can be constructed from a number of traces of othersymbols. As all traces belong to a subfield of the defining field of the RScode and many of them are linearly dependent, the total repair bandwidth issignificantly reduced compared to that of the naive repair scheme. We extendthe trace collection technique to cope with multiple erasures.